package hyy_2022;

/**
 * 青蛙跳台阶问题
 * 跳一级台阶,1种跳法 f(1) = 1
 *
 * 跳二级台阶,2种跳法 f(2) = 2
 *
 * 跳三级台阶,分析一下:
 * 假设最后一跳是两步,则三级台阶的跳法 = 一级台阶的跳法  等价于:f(3) = f(1)
 * 假设最后一跳是一步,则三级台阶的跳法 = 二级台阶的跳法  等价于:f(3) = f(2)
 * 总结下来 f(3) = f(2) + f(1)
 *
 * 跳四级台阶,分析一下
 *  假设最后一跳是两步,则四级台阶的跳法 = 二级台阶的跳法 等价于:f(4) = f(2)
 *  假设最后一跳是一步,则四级台阶的跳法 = 三级台阶的跳法 等价于:f(4) = f(3)
 * 总结下来 f(4) = f(3) + f(2)
 *
 * 所以青蛙跳台阶(1 1 2 3 5) 等价于 斐波拉契数列(0 1 1 2 3)
 *
 */
public class _0805_Offer10_II_NumWays {

    public int numWays(int n) {
        final  int MOD = 1000000007;
        if(n < 2) {
            return  1;
        }
        int p = 0, q = 1, r = 1;
        while(n > 1) {
            p = q;
            q = r;
            r = (p+q) % MOD;
            n -- ;
        }
        return r;
    }

}
